/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {  //贪心算法
  let maxJump = nums.length - 1; //放到最后一个位置
  for (let i = nums.length - 2; i >= 0; i--) {
    if (i + nums[i] >= maxJump) {
      maxJump = i;
    }
  }
  return maxJump === 0;
};


//  var canJump = function (nums) { //bottom up
//     const totallentgth = nums.length;
//     const memo = Array(totallentgth).fill(0)
//     memo[totallentgth - 1] = 1
//     for(let i = totallentgth -2; i >=0 ; i--){
//         const maxJump = Math.min(i+nums[i],totallentgth -1)
//         for(let j=i+1;j<=maxJump;j++){
//             if(memo[j]===1){
//                 memo[i] =1 
//                 break
//             }
//         }
//     }
//     if(memo[0]===1){
//         return true 
//     }else {
//         return false
//     }
//  }


 // 动态规划 top down 树 
 //https://www.bilibili.com/video/BV1wA411b7qZ
// var canJump = function (nums) {
//     const totallentgth = nums.length;
//     const memo = Array(totallentgth).fill(0)
//     memo[totallentgth - 1] = 1
//     function jump(position) {
//         if (memo[position] === 1) {
//             return true
//         } else if (memo[position] === -1) {
//             return false
//         }

//         const maxJump = Math.min(position + nums[position], totallentgth - 1)
//         for (let i = position + 1; i <= maxJump; i++) {
//             const jumpResult = jump(i)
//             if (jumpResult === true) {
//                 memo[position] = 1
//                 return true
//             }
//         }
//         memo[position] = -1
//         return false
//     }
//     let result = jump(0)
//     return result
// }


 